package com.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class P0260SingleNumberIII {

	
	public static void main(String[] args) {
//		System.out.println(singleNumber(1994));
		int[] num = {1,2,1,3,2,5};
		singleNumber2(num);
	}
	
    public static int[] singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        
        for(int item : nums) {
        	if(!set.add(item)) {
        		set.remove(item);
        	}
        }
        
        Integer[] res = new Integer[2];
        set.toArray(res);
        
        int[] ress = Arrays.stream(res).mapToInt(Integer::valueOf).toArray();
        
        return ress;
    }


    /**
     * 位运算解决方法
     * @param nums
     * @return
     */
    public static int[] singleNumber2(int[] nums) {
        int AXORB = 0;
        for (int num : nums) {
            AXORB ^= num; 
        }
        // pick one bit as flag
        int bitFlag = (AXORB & (~ (AXORB - 1)));
        int[] res = new int[2];
        for (int num : nums) {
            if ((num & bitFlag) == 0) {
                res[0] ^= num;
            } else {
                res[1] ^= num;
            }
        }
        return res;
    }
    
    
	
}
